package J2_8;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class test {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }


    }

    //给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.empty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;

        }
        return list;

    }


    //给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历

    public List<Integer> postorderTraversal1(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode top = new TreeNode();
        while (root != null || !stack.empty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.peek();
            if (root.right != null && root.right != top) {
                root = root .right;
            }else {
                list.add(root.val);
                top = root;
                stack.pop();
                root = null;
            }

        }
        return list;
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            while (!stack.empty()) {
                TreeNode cur = stack.peek();
                if (cur.right == null && cur.left == null) {
                    stack.pop();
                    list.add(cur.val);
                    break;
                }
                if (cur.right != null) {
                    stack.push(cur.right);
                    cur.right =null;
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                    cur.left = null;
                }
            }
        }
        return list;
    }

}
